|
In computer science, fractional cascading is a technique to speed up a sequence of binary searches for the same value in a sequence of related data structures. The first binary search in the sequence takes a logarithmic amount of time, as is standard for binary searches, but successive searches in the sequence are faster. The original version of fractional cascading, introduced in two papers by Chazelle and Guibas in 1986 (; ), combined the idea of cascading, originating in range searching data structures of and , with the idea of fractional sampling, which originated in . Later authors introduced more complex forms of fractional cascading that allow the data structure to be maintained as the data changes by a sequence of discrete insertion and deletion events. ==Example== As a simple example of fractional cascading, consider the following problem. We are given as input a collection of ''k'' ordered lists ''L''''i'' of real numbers, such that the total length Σ|''L''''i''| of all lists is ''n'', and must process them so that we can perform binary searches for a query value ''q'' in each of the ''k'' lists. For instance, with ''k'' = 4 and ''n'' = 17, :''L''1 = 2.4, 6.4, 6.5, 8.0, 9.3 :''L''2 = 2.3, 2.5, 2.6 :''L''3 = 1.3, 4.4, 6.2, 6.6 :''L''4 = 1.1, 3.5, 4.6, 7.9, 8.1 The simplest solution to this searching problem is just to store each list separately. If we do so, the space requirement is O(''n''), but the time to perform a query is O(''k'' log(''n''/''k'')), as we must perform a separate binary search in each of ''k'' lists. The worst case for querying this structure occurs when each of the ''k'' lists has equal size ''n''/''k'', so each of the ''k'' binary searches involved in a query takes time O(log(''n''/''k'')). A second solution allows faster queries at the expense of more space: we may merge all the ''k'' lists into a single big list ''L'', and associate with each item ''x'' of ''L'' a list of the results of searching for ''x'' in each of the smaller lists ''L''''i''. If we describe an element of this merged list as ''x''() where ''x'' is the numerical value and ''a'', ''b'', ''c'', and ''d'' are the positions (the first number has position 0) of the next element at least as large as ''x'' in each of the original input lists (or the position after the end of the list if no such element exists), then we would have :''L'' = 1.1(), 1.3(), 2.3(), 2.4(), 2.5(), 2.6(), ::3.5(), 4.4(), 4.6(), 6.2(), 6.4(), 6.5(), ::6.6(), 7.9(), 8.0(), 8.1(), 9.3() This merged solution allows a query in time O(log ''n'' + ''k''): simply search for ''q'' in ''L'' and then report the results stored at the item ''x'' found by this search. For instance, if ''q'' = 5.0, searching for ''q'' in ''L'' finds the item 6.2(), from which we return the results ''L''1() = 6.4, ''L''2() (a flag value indicating that ''q'' is past the end of ''L''2), ''L''3() = 6.2, and ''L''4() = 7.9. However, this solution pays a high penalty in space complexity: it uses space O(''kn'') as each of the ''n'' items in ''L'' must store a list of ''k'' search results. Fractional cascading allows this same searching problem to be solved with time and space bounds meeting the best of both worlds: query time O(log ''n'' + ''k''), and space O(''n''). The fractional cascading solution is to store a new sequence of lists ''M''''i''. The final list in this sequence, ''M''''k'', is equal to ''L''''k''; each earlier list ''M''''i'' is formed by merging ''L''''i'' with every second item from ''M''''i'' + 1. With each item ''x'' in this merged list, we store two numbers: the position resulting from searching for ''x'' in ''L''''i'' and the position resulting from searching for ''x'' in ''M''''i'' + 1. For the data above, this would give us the following lists: :''M''1 = 2.4(1 ), 2.5(1 ), 3.5(3 ), 6.4(5 ), 6.5(5 ), 7.9(5 ), 8.0(6 ), 9.3(6 ) :''M''2 = 2.3(1 ), 2.5(1 ), 2.6(1 ), 3.5(1 ), 6.2(3 ), 7.9(5 ) :''M''3 = 1.3(1 ), 3.5(1 ), 4.4(2 ), 6.2(3 ), 6.6(3 ), 7.9(3 ) :''M''4 = 1.1(0 ), 3.5(0 ), 4.6(0 ), 7.9(0 ), 8.1(0 ) Suppose we wish to perform a query in this structure, for ''q'' = 5. We first do a standard binary search for ''q'' in ''M''1, finding the value 6.4(). The "1" in 6.4(), tells us that the search for ''q'' in ''L''1 should return ''L''1() = 6.4. The "5" in 6.4() tells us that the approximate location of ''q'' in ''M''2 is position 5. More precisely, binary searching for ''q'' in ''M''2 would return either the value 7.9(5 ) at position 5, or the value 6.2(3 ) one place earlier. By comparing ''q'' to 6.2, and observing that it is smaller, we determine that the correct search result in ''M''2 is 6.2(3 ). The first "3" in 6.2(3 ) tells us that the search for ''q'' in ''L''2 should return ''L''2(), a flag value meaning that ''q'' is past the end of list ''L''2. The second "3" in 6.2(3 ) tells us that the approximate location of ''q'' in ''M''3 is position 3. More precisely, binary searching for ''q'' in ''M''3 would return either the value 6.2(3 ) at position 3, or the value 4.4(2 ) one place earlier. A comparison of ''q'' with the smaller value 4.4 shows us that the correct search result in ''M''3 is 6.2(). The "2" in 6.2() tells us that the search for ''q'' in ''L''3 should return ''L''3() = 6.2, and the "3" in 6.2() tells us that the result of searching for ''q'' in ''M''4 is either ''M''4() = 7.9() or ''M''4() = 4.6(); comparing ''q'' with 4.6 shows that the correct result is 7.9() and that the result of searching for ''q'' in ''L''4 is ''L''4() = 7.9. Thus, we have found ''q'' in each of our four lists, by doing a binary search in the single list ''M''1 followed by a single comparison in each of the successive lists. More generally, for any data structure of this type, we perform a query by doing a binary search for ''q'' in ''M''1, and determining from the resulting value the position of ''q'' in ''L''1. Then, for each ''i'' > 1, we use the known position of ''q'' in ''M''''i'' to find its position in ''M''''i'' + 1. The value associated with the position of ''q'' in ''M''''i'' points to a position in ''M''''i'' + 1 that is either the correct result of the binary search for ''q'' in ''M''''i'' + 1 or is a single step away from that correct result, so stepping from ''i'' to ''i'' + 1 requires only a single comparison. Thus, the total time for a query is O(log ''n'' + ''k''). In our example, the fractionally cascaded lists have a total of 25 elements, less than twice that of the original input. In general, the size of ''M''''i'' in this data structure is at most : as may easily be proven by induction. Therefore, the total size of the data structure is at most : as may be seen by regrouping the contributions to the total size coming from the same input list ''Li'' together with each other. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「fractional cascading」の詳細全文を読む スポンサード リンク
|